/**
 * Dijkstra算法实现（前端版本）
 */
export class DijkstraAlgorithm {
  constructor(graph) {
    this.graph = graph
    this.distances = {}
    this.previousNodes = {}
    this.unvisitedNodes = []
  }

  findShortestPath(startNode, endNode) {
    this._initialize(startNode)

    while (this.unvisitedNodes.length > 0) {
      const currentNode = this._getClosestUnvisitedNode()
      if (currentNode === endNode) {
        break
      }
      this._updateNeighborDistances(currentNode)
    }

    return {
      path: this._buildPath(endNode),
      distance: this.distances[endNode]
    }
  }

  _initialize(startNode) {
    this.distances = {}
    this.previousNodes = {}
    this.unvisitedNodes = []

    for (const node in this.graph) {
      this.distances[node] = Infinity
      this.unvisitedNodes.push(node)
    }

    this.distances[startNode] = 0
  }

  _getClosestUnvisitedNode() {
    let closestNode = null
    let minDistance = Infinity

    for (const node of this.unvisitedNodes) {
      if (this.distances[node] < minDistance) {
        minDistance = this.distances[node]
        closestNode = node
      }
    }

    if (closestNode !== null) {
      const index = this.unvisitedNodes.indexOf(closestNode)
      this.unvisitedNodes.splice(index, 1)
    }

    return closestNode
  }

  _updateNeighborDistances(currentNode) {
    const neighbors = this.graph[currentNode] || {}

    for (const neighbor in neighbors) {
      if (!this.unvisitedNodes.includes(neighbor)) {
        continue
      }

      const weight = neighbors[neighbor]
      const newDistance = this.distances[currentNode] + weight

      if (newDistance < this.distances[neighbor]) {
        this.distances[neighbor] = newDistance
        this.previousNodes[neighbor] = currentNode
      }
    }
  }

  _buildPath(endNode) {
    const path = []
    let current = endNode

    while (current !== undefined) {
      path.unshift(current)
      current = this.previousNodes[current]
    }

    return path
  }
}

